﻿//数据流的中位数(hard): https://leetcode.cn/problems/find-median-from-data-stream/
class MedianFinder{
    priority_queue<int,vector<int>,greater<int>> right;  //小堆
    priority_queue<int> left;  //大堆
public:
    MedianFinder() 
    {}
    
    
    void addNum(int num) {
        if(left.size()==0||num<=left.top())
        {
            left.push(num);
        }
        else
        {
            right.push(num);
        }
        int m=left.size();
        int n=right.size();
        if(n-m==1)
        {
            int out=right.top();
            right.pop();
            left.push(out);
        }
        if(m-n==2)
        {
            int out=left.top();
            left.pop();
            right.push(out);
        }
    }
    
    double findMedian() {
        int m=left.size();
        int n=right.size();
        if(m==n)  return (left.top()+right.top())/2.0;
        else      return left.top();
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */